home *** CD-ROM | disk | FTP | other *** search
/ Amiga Packmags / Source, The - Issue 5 (1993)(Epsilon)[WB].zip / Source, The - Issue 5 (1993)(Epsilon)[WB].adf / Source / Vectors / VectorSpace / PointsInCircle.lha / pointsncircle2.txt < prev   
Internet Message Format  |  1989-10-24  |  3KB
  1. From albanycs!leah:rsb584 Wed Apr  6 17:30:46 1988
  2. Received: by albanycs.albany.edu (5.54/4.8)
  3.     id AA28065; Wed, 6 Apr 88 11:55:31 EST
  4. Date: Wed, 6 Apr 88 12:55:22 EDT
  5. From: albanycs!leah:rsb584 (Raymond S Brand)
  6. Received: by leah.Albany.EDU (5.58/1.1)
  7.     id AA02145; Wed, 6 Apr 88 12:55:22 EDT
  8. Message-Id: <8804061655.AA02145@leah.Albany.EDU>
  9. To: albanycs:beowulf!rsbx
  10. Subject: circlept3.txt
  11.  
  12. >From guy@SHERLOCK.PC.CS.CMU.EDU Mon Apr  4 23:05:59 1988
  13. Path: leah!itsgw!nysernic!cmx!batcomputer!cornell!rochester!PT.CS.CMU.EDU!SHERLOCK.PC.CS.CMU.EDU!guy
  14. From: guy@SHERLOCK.PC.CS.CMU.EDU (Guy Jacobson)
  15. Newsgroups: comp.graphics
  16. Subject: Re: Algorithm wanted: Circle enclosing points
  17. Summary: The answer.
  18. Message-ID: <1314@PT.CS.CMU.EDU>
  19. Date: 5 Apr 88 03:05:59 GMT
  20. References: <wWIfSMy00Xo3A5u1dC@andrew.cmu.edu>
  21. Sender: netnews@PT.CS.CMU.EDU
  22. Organization: Carnegie-Mellon University, CS/RI
  23. Lines: 34
  24.  
  25. This is an old and very basic problem in computational geometry (and
  26. operations research) first posed by Sylvester in 1857 [J. J. Sylvester, `` A
  27. Question in the Geometry of Situation'', _Quart._J._Math._ 1 (1857)].  The
  28. problem has received much attention over the years.  In 1982, Megiddo showed
  29. how to solve the problem in linear time, improving on the previous n log n
  30. bound of Hoey and Shamos [N. Megiddo, ``Linear-time Algorithms for Linear
  31. Programming in R^3 and Related Problems'', in Proc. 23rd. FOCS (1982), pp.
  32. 329-338].
  33.  
  34. TRUE FACT:  The smallest circle enclosing all the points is a circle with
  35. two of the points as a diameter (if some such circle encloses all the other
  36. points), or the circumscribing circle of three (or more, in degenerate
  37. cases) of the points.  Think of a circularly constrained hoop shrinking in
  38. from infinity to convince yourself of this.
  39.  
  40. The naive algorithm generates all pairs of points (as potential diameters)
  41. and checks if all the other points are inside the circle with those pairs as
  42. diameters.  If such pairs exist, the one with smallest diameter defines the
  43. smallest enclosing circle.  If no pair forms the diameter of an enclosing
  44. circle, then all triples are checked; again the triple whose circumscribing
  45. circle encloses all the points with smallest diameter defines the desired
  46. circle (this HAS To succeed, from the TRUE FACT above).  This algorithm
  47. takes n^4 time as presented.
  48.  
  49. Hoey and Shamos's algorithm uses the farthest-point Voronoi diagram, and was
  50. the first algorithm proved to run in o(n^3) time.
  51.  
  52. Megiddo's algorithm is too complex to be included here.  It proceeds to make
  53. a series of passes through the points, discarding those that cannot possibly
  54. be on the boundary of the desired circle.  In each pass, it is guaranteed to
  55. discard at least a fixed fraction (1/16) of the points from consideration;
  56. this proves the linear time bound.
  57.  
  58. -- Guy
  59.  
  60.  
  61.